#define  _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef int KeyType;
typedef struct
{
	KeyType key;
}ElmeType;
typedef struct
{
	ElmeType r[MAX_SIZE + 1];
	int length;
}SqList;

void IsertSort(SqList& L)
{
	int i, j;
	for (i = 2; i <= L.length; i++)
	{
		if (L.r[i].key < L.r[i - 1].key)
		{
			L.r[0].key = L.r[i]. key;
			for (j = i - 1; L.r[0].key < L.r[j].key; j--)
			{
				L.r[j + 1] = L.r[j];
			}
			L.r[j + 1].key = L.r[0].key;
		}
	}
}



void ShellSort(SqList& L, int d[], int m)
{
	int k, i, j;
	for (k = 0; k < m; k++)
	{
		for (i = d[k]; i <= L.length; i++)
		{
			if (L.r[i].key < L.r[i - d[k]].key)
			{
				L.r[0].key = L.r[i].key;
				for (j = i - d[k]; j > 0 && L.r[0].key < L.r[j].key; j -= d[k])
				{
					L.r[j + d[k]].key = L.r[j].key;
				}
 			}
			L.r[j + d[k]].key = L.r[0].key;
		}
	}
}

void BubbleSort(SqList &L)
{
	ElmeType tmp;
	for (int i = L.length - 1, exchanged = 1; exchanged && i >= 1; i--)
	{
		exchanged = 0;
		for (int j = 1; j <= i; j++)
		{
			if (L.r[j].key > L.r[j + 1].key)
			{
				tmp = L.r[j];
				L.r[j] = L.r[j + 1];
				L.r[j + 1] = tmp;
				exchanged = 1;
			}
		}
	}
}


void QuickSort(SqList& L, int low, int high)
{
	if (low < high)
	{
		int i = low;
		int  j = high;
		L.r[0].key = L.r[i].key;
		while (i < j)
		{
			while (L.r[j].key >= L.r[0].key && i < j)
				j--;
			L.r[i] = L.r[j];
			while (L.r[i].key <= L.r[0].key && i < j)
				i++;
			L.r[j] = L.r[i];
		}
		L.r[i] = L.r[0];
		QuickSort(L, low, i - 1);
		QuickSort(L, i + 1, high);
	}
}


void SelectSort(SqList& L)
{
	ElmeType tmp;
	for (int i = 1; i <= L.length; i++)
	{
		int min = i;
		for (int j = i + 1; j <= L.length; j++)
			if (L.r[j].key < L.r[min].key)
				min = j;
		if (min != i)
		{
			tmp = L.r[min];
			L.r[min] = L.r[i];
			L.r[i] = tmp;
		}
	}
}

void MergeSort(SqList& L, SqList& T, int low, int high)
{
	int m, i, j, p;
	if (low < high)
	{
		m = (low + high) / 2;
		MergeSort(L, T, low, m - 1);
		MergeSort(L, T, m + 1, high);
		
		i = low, j = m + 1, p = low;
		while (i <= m && j <= high)
			if (L.r[i].key < L.r[j].key)
				T.r[p++] = T.r[i++];
			else
				T.r[p++] = T.r[j++];
	}
	while (i <= m)
		T.r[p++] = T.r[i++];
	while (j <= high)
		T.r[p++] = T.r[j++];
	for (p = low, i = low; i <= high; p++, i++)
		L.r[i] = T.r[p];
}